export class PriorityQueue {
  queue: any[] = [];
  compare: (a: any, b: any) => number = (a, b) => {
    return a < b ? -1 : a === b ? 0 : 1;
  };

  constructor(compare?: (a: any, b: any) => number) {
    if (compare !== undefined) {
      this.compare = compare;
    }
  }

  /**
   * 长度属性
   * @date 2023/8/2 - 17:33:20
   *
   * @readonly
   * @type {*}
   */
  get length() {
    return this.queue.length;
  }

  /**
   * Top 元素
   * @date 2023/9/6 - 19:40:22
   *
   * @readonly
   * @type {any}
   */
  get top() {
    return this.queue[0];
  }

  /**
   * 入队
   * @date 2023/8/2 - 17:33:06
   *
   * @param {*} obj
   */
  push(obj: any) {
    this.queue.push(obj);
    this._shiftUp(this.length - 1);
    // this.checkInvalidate();
  }

  /**
   * 弹出最小值
   * @date 2023/8/2 - 17:32:52
   *
   * @returns {*}
   */
  pop() {
    if (this.length <= 0) {
      return undefined;
    }

    this._swap(0, this.length - 1);
    let ret = this.queue.pop();
    this._shiftDown(0);
    // this.checkInvalidate();
    return ret;
  }

  /**
   * 判断包含指定对象
   * @date 2023/8/2 - 17:32:30
   *
   * @param {*} obj
   * @returns {*}
   */
  has(obj: any) {
    return this.queue.findIndex((src) => this.compare(src, obj) !== -1);
  }

  /**
   * 移除指定对象
   * @date 2023/8/2 - 17:32:10
   *
   * @param {*} obj
   * @returns {*}
   */
  remove(obj: any) {
    let i = this.queue.findIndex((src) => this.compare(src, obj) === 0);
    if (i === -1) {
      console.log(`remove obj ${obj} failed!!!`);
      return;
    }

    this._swap(i, this.length - 1);
    let ret = this.queue.pop();
    let p = Math.floor((i - 1) / 2);
    if (p >= 0 && i < this.length) {
      if (this._lessThan(i, p)) {
        this._shiftUp(i);
      } else {
        this._shiftDown(i);
      }
    }
    // this.checkInvalidate();
    return ret;
  }

  checkInvalidate() {
    for (let i = 0; i < this.length; i++) {
      let l = 2 * i + 1;
      let r = 2 * i + 2;
      if (l >= this.length) {
        break;
      }
      if (this._lessThan(l, i)) {
        throw `bad priority q for parent >= left, i: ${i} value: ${this.queue[i]} left: ${this.queue[l]}`;
      }

      if (r >= this.length) {
        break;
      }
      if (this._lessThan(r, i)) {
        throw `bad priority q for parent >= right, i: ${i} value: ${this.queue[i]} right: ${this.queue[r]}`;
      }
    }
  }

  /**
   * 向上调整
   * @date 2023/8/2 - 17:33:34
   *
   * @param {number} i
   */
  _shiftUp(i: number) {
    if (i < 0 || i >= this.queue.length) {
      return;
    }

    while (i > 0) {
      let p = Math.floor((i - 1) / 2);
      if (!this._lessThan(i, p)) {
        break;
      }
      this._swap(i, p);
      i = p;
    }
  }

  /**
   * 向下调整
   * @date 2023/8/2 - 17:33:48
   *
   * @param {number} p
   */
  _shiftDown(p: number) {
    let max = Math.floor((this.length - 2) / 2);
    while (p <= max) {
      let i = 2 * p + 1;
      if (i + 1 < this.length && this._lessThan(i + 1, i)) {
        i = i + 1;
      }

      if (this._lessThan(p, i)) {
        break;
      }
      this._swap(p, i);
      p = i;
    }
  }

  _swap(i: number, j: number) {
    let t = this.queue[i];
    this.queue[i] = this.queue[j];
    this.queue[j] = t;
  }

  _lessThan(i, j) {
    return this.compare(this.queue[i], this.queue[j]) < 0;
  }
}
